package main

/*
和组合一样，只是判断条件不同而已，
就是当当前和相等才添加进结果集
剪枝操作是当前和大于0时退出循环
*/
var (
	path216 []int
	ans     [][]int
	sum     int
)

func combinationSum3(k int, n int) [][]int {
	ans = make([][]int, 0)
	bt2(n, k, 1)
	return ans
}

func bt2(n, k, startIdx int) {
	if len(path) == k && sum == n {
		tmp := make([]int, k)
		copy(tmp, path)
		ans = append(ans, tmp)
		return
	}

	for i := startIdx; i <= 9-(k-len(path))+1; i++ {
		sum += i
		path216 = append(path, i)
		if sum > n {
			sum -= i
			path216 = path216[:len(path)-1]
			return
		}
		bt2(n, k, i+1)
		sum -= i
		path216 = path216[:len(path)-1]
	}
}
